/*
 * @lc app=leetcode.cn id=494 lang=golang
 *
 * [494] 目标和
 */
package Solutions

// @lc code=start
func findTargetSumWays(nums []int, target int) int {
	sum := 0
	for _, v := range nums {
		sum += v
	}
	if sum < target {
		return 0
	}
	mp := make(map[int]int)
	mp[0] = 0
	for _, v := range nums {
		newMp := make(map[int]int)
		sum -= v
		for k, vv := range mp {
			if k+v-sum <= target {
				newMp[k+v] += vv
			}
			if k-v+sum >= target {
				newMp[k-v] += vv
			}
		}
		mp = newMp
	}
	return mp[target]
}

// @lc code=end
